package Company;

import java.util.*;
class Solution {
    List<List<Integer>>res=new LinkedList<>();
    boolean[]used;
    LinkedList <Integer>track=new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {

        used=new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums);
        return res;
    }

    void backtrack(int []nums)
    {
        if(track.size()==nums.length)
        {
            res.add(new LinkedList(track));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(used[i])
            {
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1])
            {
                continue;
            }
            track.add(nums[i]);
            used[i]=true;
            backtrack(nums);
            track.removeLast();
            used[i]=false;
        }
    }
}
/**
 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
  }

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head;
        ListNode low=head;
        for(int i=0;i<k;i++)
        {
            fast=fast.next;
        }
        while(fast!=null)
        {
            low=low.next;
            fast=fast.next;
        }
        return low;
    }
}*/
/**
 class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head==null)
        {
            return null;
        }
        if(head.val==val)
        {
            return head.next;
        }
        ListNode prev=head;
        while(prev!=null&&prev.next!=null)
        {if(prev.next.val==val)
        {
            prev.next=prev.next.next;

        }
            prev=prev.next;

        }
        return head;

    }
}*/
/**
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer>ret=new ArrayList<>();
        int x=0;
        int y=0;
        for(int i=left;i<=right;i++)
        {    x=i;
            int flag=1;
            while(x>0) {
                y = x % 10;
                x = x / 10;
                if (y== 0||i%y!=0) {//如果这个数中有0的话，自动跳出循环
                    flag=0;
                }
                flag=flag*flag;
            }
            if(flag==1)
            {
                ret.add(i);
            }

        }
        return ret;
    }
}*/
/**class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int[] dp = new int[str.length() + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= str.length(); i++) {
            String tmpStr = str.substring(i - 2, i);
            if (tmpStr.compareTo("10") >= 0 && tmpStr.compareTo("25") <= 0) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[dp.length - 1];
    }
}*/
/**
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character>set=new HashSet<>();
        int  left=0;
        int right=left+1;
        int max=0;
        int count=0;

        while(left<s.length())
        {
            for(int i=left;i<s.length();i++)
            {
                if(set.contains(s.charAt(i)))
                {
                    set.clear();
                    count=0;
                    break;
                }

                set.add(s.charAt(i));
                count++;
                max=Math.max(count,max);

            }
            left++;
        }
        return max;

    }
}*/
/**
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
         this.right = right;
      }
  }

class Solution {
    List<List<Integer>>ret=new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        LinkedList<Integer>traback=new LinkedList<>();

        if(root==null)
        {
            return ret;
        }
        dfs(root,target,traback);
        return ret;

    }
    public void dfs(TreeNode root,int target,LinkedList<Integer>traback)
    {
        if(root==null)
        {
            return;
        }

        traback.add(root.val);//装节点值
        target-=root.val;

        if(root.left==null&&root.right==null&&target==0)//如果已经走到了叶子节点
        {
            ret.add(new LinkedList(traback));

        }
        dfs(root.left,target,traback);//遍历每个根节点的右子树
        dfs(root.right,target,traback);//遍历每个根节点的右子树
        traback.removeLast();//如果某个节点不满足，返回做其他选择
    }
}*/
/**
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //基础的判空操作
        //根据二叉搜索数的性质，根节点大于左子树的小于右子树
        if(postorder==null||postorder.length==0)
        {
            return true;
        }
        return Help(postorder,0,postorder.length-1);
    }
    public boolean Help(int []postorder,int start,int end)
    {
        if(start>=end)
        {
            return true;
        }
        int i=start;
        //后续遍历，最后一个节点就是根节点
        int root=postorder[end];
        //分区间，筛选出小于root的节点和大于root的节点
        while(i<=end&&postorder[i]<root)
        {//统计小于root的节点
            i++;
        }
        //如果根的右子树有小于根的节点，返回false
        for(int j=i;j<=end;j++)
        {
            if(postorder[j]<root)
            {
                return false;
            }
        }

        return Help(postorder,start,i-1) && Help(postorder,i,end-1);
    }
}*/
/**
class Solution {
    //dp数组存储的是每一步的结果，
    public int maxValue(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int [][]dp=new int[m+1][n+1];
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}*/
/**class Solution {
    public int maxSubArray(int[] nums) {
        int []dp=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++)
        {
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}*/
/**
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer>stack=new Stack<>();
        int x=0;

        if(pushed==null||popped==null||(pushed.length!=popped.length))
        {
            return false;
        }
        for(int i=0;i<pushed.length;i++)
        {
            stack.push(pushed[i]);
            while(!stack.empty()&&stack.peek()==popped[x])
            {
                stack.pop();
                x++;
            }

        }

        if(stack.empty())
        {
            return true;
        }
        return false;
    }
}*/
/**
class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
*/

/**
class Solution {
public int maxProfit(int[] prices) {

        int  res=0;
        for(int i=1;i<prices.length;i++)
        {
        res=Math.max(res,prices[i]-prices[i-1]);
        prices[i]=Math.min(prices[i],prices[i-1]);
        }
        return res;
        }
        }*/
/**
class Solution {
    public int numWays(int n) {
        if(n<2)
        {
            return 1;
        }
        int first=1;
        int second=1;
        int third=0;
        while(n-->0)
        {
            third=(first+third)%1000000007;
            first=second;
            second=third;
        }
        return third;
    }
}*/
/**
class Solution {
    public int fib(int n) {
        int fast=0;
        int third=1;
        int second=1;
        if(n==0)
        {
            return 0;
        }
        if(n<3)
        {
            return 1;
        }
        n=n-1;
        while(n-->0)
        {
            third=(fast+second)%1000000007;
            fast=second;
            second=third;
        }
        return third;
    }
}*/
/**
 class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
     TreeNode(int x) { val = x; }
  }

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //isSame函数，传入两个树的根节点，判断是否相同（两树的根节点相同）
        if(A==null||B==null)//  全为null
        {
            return false;
        }
        boolean result=false;
        if(A.val==B.val) //在A树中找到了B数的根节点
        {
            result=isSame(A,B);//判断B是否是A的子树结构
        }
        if(result!=true) //A数和B数的根节点不相同，从A的左子树开始寻找
        {
            result=isSubStructure(A.left,B);//递归查找
        }
        if(result!=true)//左子树中未找到B的根节点，开始寻找A的右子树
        {
            result=isSubStructure(A.right,B);
        }
        return result;

    }

    boolean isSame(TreeNode A,TreeNode B)//传入两个子树的根节点，判断是否相同
    {
        if(B==null)
        {
            return true;
        }
        if(A==null)
        {
            return false;
        }
        if(A.val!=B.val)//根节点不相等，子树肯定不相同
        {
            return  false;
        }
        return isSame(A.left,B.left)&&isSame(A.right,B.right);//递归查找左子树的和右子树
    }

}*/
/**
 class ListNode {
     int val;
      ListNode next;
      ListNode(int x) { val = x; }
 }
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)
        {
            return head;
        }
        ListNode left=head;
        ListNode mid=left.next;
        ListNode right=mid.next;
        while(right!=null)
        {
            mid.next=left;
            left=mid;
            mid=right;
            right=right.next;
        }
        mid.next=left;
        head.next=null;
        return mid;
    }
}*/
/**
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}*/
/**
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
        {
            return true;
        }
        return build(root.left,root.right);

    }
    boolean build(TreeNode root1,TreeNode root2)
    {
        if(root1==null&&root2!=null)
        {
            return false;
        }
        if(root1!=null&&root2==null)
        {
            return false;
        }
        if(root1==null&&root2==null)
        {
            return true;
        }
        return (root1.val==root2.val&&build(root1.left,root2.right)&&build(root1.right,root2.left));
    }
}*/
/**
class Solution {
    public boolean hasAlternatingBits(int n) {
        int prev = 2;
        while (n != 0) {
            int cur = n % 2;
            if (cur == prev) {
                return false;
            }
            prev = cur;
            n /= 2;
        }
        return true;
    }
}*/
/**
class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length, cnt = m + n;
        int t = mean * cnt;
        for (int i : rolls) t -= i;
        if (t < n || t > 6 * n) return new int[0];

        int[] ans = new int[n];
        Arrays.fill(ans, t / n);
        if (t / n * n < t) {
            int d = t - (t / n * n), idx = 0;
            while (d-- > 0) ans[idx++]++;
        }
        return ans;
    }
}*/
/**
class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }
class Solution {
    public int[] levelOrder(TreeNode root) {
        //先打印左子树再打印右子树
        Deque<TreeNode>stack=new ArrayDeque<>();
        LinkedList<Integer>ret=new LinkedList<>();
        int []nums=new int[0];
        if(root==null)
        {
            return nums;
        }
        stack.push(root);
        while(!stack.isEmpty())
        {
            int size=stack.size();
            TreeNode cur=stack.poll();
            ret.add(cur.val);
            if(cur.left!=null)
            {
                stack.add(cur.left);

            }
            if(cur.right!=null)
            {
                stack.add(cur.right);

            }


        }
        int []arr=new int [ret.size()];
        for(int i=0;i<ret.size();i++)
        {
            arr[i]=ret.get(i);
        }
        return arr;
    }
}*/
/**
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return ans;
        queue.add(root);
        int level = 1;
        while (!queue.isEmpty())
        {
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(level % 2 != 0)
                {
                    if (node.left != null) stack.push(node.left);
                    if (node.right != null) stack.push(node.right);
                }else{
                    if (node.right != null) stack.push(node.right);
                    if (node.left != null) stack.push(node.left);
                }
            }
            int stack_size = stack.size();
            for (int i = 0; i < stack_size; i++) {
                queue.add(stack.pop());
            }
            ans.add(tmp);
            level++;
        }
        return ans;

    }
}*/
/**
class Solution {

    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        List<List<Integer>> ans = new ArrayList<>();
        //list1和list2存储不同于对方的整数
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        //先将nums1和nums2中的数据存入哈希表中
        for (int i = 0; i < nums1.length; i++) set1.add(nums1[i]);
        for (int i = 0; i < nums2.length; i++) set2.add(nums2[i]);
        for (int i = 0; i < nums1.length; i++) {
            //防止重复添加
            if (!set2.contains(nums1[i]) && !list1.contains(nums1[i])) list1.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            //防止重复添加
            if (!set1.contains(nums2[i]) && !list2.contains(nums2[i])) list2.add(nums2[i]);
        }
        ans.add(list1);
        ans.add(list2);
        return ans;

    }
}*/
/**
class MyQueue {

    private Stack<Integer> a;// 输入栈
    private Stack<Integer> b;// 输出栈

    public MyQueue() {
        a=new Stack<>();
        b=new Stack<>();
    }

    public void push(int x) {
        a.push(x);
    }

    public int pop() {
        if(b.isEmpty())
        {
            while(!a.isEmpty())
            {
                b.push(a.pop());
            }
        }
        return b.pop();
    }

    public int peek() {
        if(b.isEmpty())
        {
            while(!a.isEmpty())
            {
                b.push(a.pop());
            }
        }
        return b.peek();
    }

    public boolean empty() {
        return a.isEmpty()&&b.isEmpty();

    }
}*/
/**
class Solution {
    public int minDeletion(int[] nums) {
        int ans = 0;
        int n=nums.length;
        if(n==0) return 0;
        int cnt=0; // 记录删除的数量
        for(int i=0;i<n-1;i++){
            if(((i-cnt)%2)==0){ // 如果当前下标 左移后为偶数
                if(nums[i]==nums[i+1]){ // 如果和后面的数一样，就删除当前的数
                    cnt++;
                }
            }
        }
        if(((n-cnt)%2)==1){  // 如果删完了，数组长度为奇数，就再删除最后一个数
            cnt++;
        }
        return cnt;
    }
}
*/

/**
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else if (nums[pivot] > nums[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return nums[low];
    }
}*/
/**
class Solution {


    public char firstUniqChar(String s) {
        if (s.equals("")) return ' ';
        //创建‘a'-'z'的字典
        int[] target = new int[26];
        //第一次遍历，将字符统计到字典数组
        for (int i = 0; i < s.length(); i++) {
            target[s.charAt(i) - 'a']++;
        }
        //第二次遍历，从字典数组获取次数
        for (int i = 0; i < s.length(); i++) {
            if (target[s.charAt(i) - 'a'] == 1) return s.charAt(i);
        }

        return ' ';
    }


}*/
/**
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {

        if(matrix == null || matrix.length == 0) {
            return false;
        }
        int i=0;
        int j=matrix[0].length-1;

        while(i<matrix.length&&j>=0)
        {
            if(target>matrix[i][j])
            {
                i++;
            }
            else if(target<matrix[i][j])
            {
                j--;
            }
            else
            {
                return true;
            }
        }
        return false;

    }
}*/
/**
class Solution {
    public int calPoints(String[] ops) {
        int sum=0;
        List<Integer>ret=new ArrayList<>();
        for(int i=0;i<ops.length;i++)
        {
            if(ops[i].charAt(0)=='C')
            {
                ret.remove(ret.size()-1);
            }
            else if(ops[i].charAt(0)=='D')
            {
                ret.add(ret.get(ret.size()-1)*2);

            }
            else if(ops[i].charAt(0)=='+')
            {
                ret.add(ret.get(ret.size()-2)+ret.get(ret.size()-1));
            }
            else
            {
                ret.add(Integer.valueOf(ops[i]));
            }
        }
        for(int i=0;i<ret.size();i++)
        {
            sum+=ret.get(i);
        }
        return sum;
    }
}*/
/**
class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        for (int d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }
}*/
/**
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}*/
/**
class Solution {
    public int search(int[] nums, int t) {
        int n = nums.length;
        if (n == 0) return 0;
        int a = -1, b = -1;

        // 二分出左边界
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= t) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != t) return 0;
        a = r;

        // 二分出右边界
        l = 0; r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= t) l = mid;
            else r = mid - 1;
        }
        if (nums[r] != t) return 0;
        b = r;

        return b - a + 1;
    }
}*/
/**
class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}*/
/**
class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer>ret=new ArrayList<>();
        dayin(head,ret);
        int []arr=new int[ret.size()];
        for(int i=0;i<ret.size();i++)
        {
            arr[i]=ret.get(i);
        }
        return arr;
    }
    void dayin(ListNode head,List<Integer>ret)
    {
        if(head==null)
        {
            return;
        }
        dayin(head.next,ret);
        ret.add(head.val);
    }
}*/
/**
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build( preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    //语义：给我一个中序遍历和前序遍历，我可以构建一颗二叉树， 每一个根节点左子树和右子树和都需要中序和前序遍历的配合，
    //前序负责提供根节点，中序负责区分左右子树
    TreeNode build(int []preorder,int prestart,int preend,int[]inorder,int instart,int inend)
    {
        if(prestart>preend)
        {
            return null;
        }
        int n=preorder[prestart];

        int index=0;

        for(int i=instart;i<=inend;i++)
        {
            if(inorder[i]==n)
            {
                index=i;
                break;

            }
        }

        int leftsize=index-instart;
        TreeNode root=new TreeNode(n);

        root.left=build(preorder,prestart+1,prestart+leftsize,inorder,instart,index-1);

        root.right=build(preorder,prestart+leftsize+1,preend,inorder,index+1,inend);
        return root;
    }
}*/
/**
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                int index = stack.pop();
                ret[index] = i - index;
            }
            stack.push(i);
        }
        return ret;
    }
}*/

/**
 class ListNode {
      int val;
     ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}*/
/**
class ListNode {
     int val;
      ListNode next;
      ListNode(int x) {
         val = x;
          next = null;
     }
  }

 class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
        {
            return null;
        }
        if(head.next==null)
        {
            return null;
        }
        ListNode low=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null)
        {
            low=low.next;
            fast=fast.next.next;
            if(low==fast)
            {
                ListNode cur=head;
                while(cur!=low)
                {
                    cur=cur.next;
                    low=low.next;
                }
                return low;
            }
        }
        return null;
    }
}*/
/**
class Solution {
    public boolean isValid(String s) {
        //借助栈来实现
        //如果识别到一个‘（’‘【’‘｛’，则压入向对应的符号
        //
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++)
        {

            if(s.charAt(i)=='(')
            {
                stack.push(')');
            }
            else if(s.charAt(i)=='[')
            {
                stack.push(']');
            }
            else if(s.charAt(i)=='{')
            {
                stack.push('}');
            }
            else if(stack.isEmpty()||stack.peek()!=s.charAt(i))
            {
                return false;
            }
            else
            {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

}*/
/**
class Solution {
    public String reverseLeftWords(String s, int n) {
        //1、StringBuilder
        //
        StringBuilder ret=new StringBuilder();
        for(int i=n;i<s.length();i++)
        {
            ret.append(s.charAt(i));
        }
        for(int i=0;i<n;i++)
        {
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
}*/
/**
class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}*/
/**
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low=0;
        int fast=numbers.length-1;
        int []arr=new int[2];
        while(low<fast)
        {
            if(numbers[low]+numbers[fast]<target)
            {
                low++;
            }
            else if(numbers[low]+numbers[fast]>target)
            {
                fast--;
            }
            else
            {
                arr[0]=low;
                arr[1]=fast;
                return arr;
            }
        }

        return arr;
    }
}*/
/**
class Solution {
public String addBinary(String a, String b) {
        StringBuilder sb=new StringBuilder();
        int i=a.length()-1;
        int j=b.length()-1;
        int c=0;//存储进位值
        while(i>=0||j>=0||c!=0)
        {
        int x=i>=0?a.charAt(i--)-'0':0;
        int y=j>=0?b.charAt(j--)-'0':0;
        c=x+y+c;
        sb.append(c%2);
        c/=2;
        }
        return sb.reverse().toString();
        }
        }
 */
/**
class Solution {
    public int[] exchange(int[] nums) {
        int left=0;

        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]%2!=0)
            {
                int j=i;
                int  temp=nums[i];
                while(left<j)
                {
                    nums[j]=nums[j-1];
                    j--;
                }
                nums[left++]=temp;
            }
        }
        return nums;
    }
}*/
/**
class Solution {
    public int majorityElement(int[] nums) {
        int num=nums.length/2;
        int x=0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!(map.containsKey(nums[i]))) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            if (map.get(nums[i]).intValue() >num) {

                x=nums[i];
            }

        }
        return x;
    }
}*/
/**
class Solution {
    public int[] countBits(int n) {

        int []nums=new int [n+1];
        for(int i=0;i<=n;i++)
        {
            if(i%2==0)
            {
                nums[i]=nums[i/2];
            }
            else
            {
                nums[i]=nums[i/2]+1;
            }
        }
        return nums;
    }
}*/
/**
class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}
*/

/**
class Solution {
    public int countCollisions(String directions) {
        char []arr=directions.toCharArray();
        int l=0;
        int r=0;
        int sum=0;
        int sum1=0;
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]=='R')
            {
                r++;
            }
            else if(arr[i]=='L'||arr[i]=='S')
            {
                sum+=r;
                r=0;
            }
        }
        for(int i=arr.length-1;i>=0;i--)
        {
            if(arr[i]=='L')
            {
                l++;
            }
            else if(arr[i]=='R'||arr[i]=='S')
            {
                sum+=l;
                l=0;
            }
        }
        return sum;
    }
}*/
/**
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

class Solution {
    Set<Integer> set = new HashSet<Integer>();

    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}
*/


/**
class Solution {
    public int countHillValley(int[] nums) {

        int res=0;
        for(int i=1;i<nums.length-1;i++)
        {
            if(nums[i]==nums[i-1])
            {
                continue;
            }
            int left = i - 1;
            int right = i + 1;
            while(right < nums.length - 1 && nums[i] == nums[right]) { // 找寻最右边的不相等邻居
                right++;
            }
            if((nums[i] > nums[left] && nums[i] > nums[right]) || (nums[i] < nums[left] && nums[i] < nums[right])) { // 若满足峰或谷要求
                res++;
            }
        }
        return res;
    }
}*/
/**
class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        char front = pattern.charAt(0), back = pattern.charAt(1);
        long sum = 0;
        int fcnt = 0, bcnt = 0;

        for(int i = text.length() - 1; i >= 0; i--) {
            char c = text.charAt(i);
            if(c == front) {
                sum += bcnt;
                fcnt++;
            }
            if(c == back){
                bcnt++;
            }
        }

        return sum + Math.max(bcnt, fcnt);
    }
}*/
/**
class Solution {
    public boolean divideArray(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for(int i=1;i<nums.length;i+=2)
        {
            sum+=nums[i]-nums[i-1];
        }
        if(sum==0)
        {
            return true;
        }
        return  false;

    }
}*/
/**
class Solution {
    public int reversePairs(int[] nums) {
        return reverPairsHelper(nums,0,nums.length-1);

    }
    int  reverPairsHelper(int []nums,int l,int r)
    {
        if(l>=r)
        {
            return 0;
        }

        int mid=l+((r-l)>>1);
        //左区间内的逆序对
        int left= reverPairsHelper(nums,l,mid);
        //右区间内的逆序对
        int right=reverPairsHelper(nums,mid+1,r);
        //两区间之间并未完全排序完成
        if(nums[mid]>nums[mid+1])
        {
            return merge(nums,l,mid,r)+left+right;
        }
        return left+right;
    }
    //统计索引为[l,mid]和[mid+1,r]之间的逆序数对
    int merge(int[]nums,int l,int mid,int r)
    {//创建一个临时的数组
        int []aux=new int[r-l+1];
        for(int i=0;i<aux.length;i++)
        {
            aux[i]=nums[i+l];
        }
        int ret=0;
        int i=l;
        int j=mid+1;
        for(int k=l;k<=r;k++)
        {//左区间已经处理完了，按顺序添加右区间剩余的数
            if(i>mid)
            {
                nums[k]=aux[j-l];
                j++;
            }
            //右区间已经处理完成，按顺序添加左区间的数
            else if(j>r)
            {
                nums[k]=aux[i-l];
                i++;
            }
            else if(aux[i-l]<=aux[j-l])
            {

                nums[k]=aux[i-l];
                i++;
            }
            else{
                ret+=(mid-i)+1;
                nums[k]=aux[j-l];
                j++;
            }
        }
        return ret;
    }
}*/
/**
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}*/
/**
 class ListNode {
      int val;
      ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public int getDecimalValue(ListNode head) {
        int x=0;
        int y=1;
        int sum=0;
        LinkedList<Integer>ret=new LinkedList<>();
        while(head!=null)
        {
            ret.add(head.val);
            head=head.next;
        }
        for(int i=ret.size()-1;i>=0;i--)
        {
            if(ret.get(i)==1)
            {
                sum+=y;
            }
            y=y*2;

        }
        return sum;
    }
}*/
/**
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);

        Set<String> set = new HashSet<>();
        String res = "";
        for (String s : words) {
            //如果单词只有一个字母，那一定是共有的
            if (s.length() == 1 || set.contains(s.substring(0, s.length() - 1))) {
                res = s.length() > res.length() ? s : res;
                set.add(s);
            }
        }
        return res;
    }
}*/
/**
class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] array = new int[words.length];
        int[] ans = new int[queries.length];
        for (int i = 0; i < array.length; i++)
            array[i] = count(words[i]);
        for (int i = 0; i < ans.length; i++) {
            int count = count(queries[i]);
            for (int j = array.length - 1; j >= 0; j--)
                ans[i]+=count < array[j]?1:0;
        }
        return ans;
    }

    // 统计最小字母出现数
    public static int count(String str) {
        int[] alphabet = new int[26];
        for (int i = 0; i < str.length(); i++)
            alphabet[str.charAt(i) - 'a']++;
        for (int count : alphabet)
            if (count != 0)
                return count;
        return 0;
    }
}*/
/**
class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Character, Integer>[] mi = new HashMap[9];
        HashMap<Character, Integer>[] mj = new HashMap[9];
        HashMap<Character, Integer>[] mx = new HashMap[9];
        for(int i=0;i<9;i++){
            mi[i] = new HashMap<>();
            mj[i] = new HashMap<>();
            mx[i] = new HashMap<>();
        }
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                Character ch=board[i][j];
                if(ch=='.')
                {
                    continue;
                }
                int x=j/3+(i/3)*3;
                mi[i].put(ch,mi[i].getOrDefault(ch,0)+1);
                mj[j].put(ch,mj[j].getOrDefault(ch,0)+1);
                mx[x].put(ch,mx[x].getOrDefault(ch,0)+1);
                if(mi[i].get(ch)>1||mj[j].get(ch)>1||mx[x].get(ch)>1){
                    return false;
                }
            }
        }
        return true;
    }
}*/
/**
class Solution {
    public boolean stoneGame(int[] piles) {
        Arrays.sort(piles);
        int sum=0;
        int sum1=0;
        for(int i=piles.length-1;i>0;i-=2)
        {
            sum+=piles[i];
        }
        for(int i=piles.length-2;i>0;i-=2)
        {
            sum1+=piles[i];
        }
        if(sum>sum1)
        {
            return true;
        }
        return false;

    }
}*/
/**
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}*/
/**
class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        Set<String> set = new HashSet<>();
        for(String word : banned) {
            set.add(word.toLowerCase());
        }
        String[] words = paragraph.split("[!?',;. ]");
        Map<String, Integer> map = new HashMap<>();
        for(String word : words) {
            if(word.equals("")) {
                continue;
            }
            if(set.contains(word.toLowerCase())) {
                continue;
            }
            int cnt = map.getOrDefault(word.toLowerCase(), 0);
            map.put(word.toLowerCase(), cnt + 1);
        }
        int count = 0;
        String ans = "";
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() > count) {
                count = entry.getValue();
                ans = entry.getKey();
            }
        }
        return ans;
    }
}*/
/**
   class ListNode {
      int val;
      ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}*/
/**
class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> index = new HashMap<String, Integer>();
        for (int i = 0; i < list1.length; i++) {
            index.put(list1[i], i);
        }

        List<String> ret = new ArrayList<String>();
        int indexSum = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (index.containsKey(list2[i])) {
                int j = index.get(list2[i]);
                if (i + j < indexSum) {
                    ret.clear();
                    ret.add(list2[i]);
                    indexSum = i + j;
                } else if (i + j == indexSum) {
                    ret.add(list2[i]);
                }
            }
        }
        return ret.toArray(new String[ret.size()]);
    }
}
*/
/**class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}*/
/**
class Solution {
    public int integerBreak(int n) {
        //dp[i]为正整数i拆分结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i - 1; ++j) {
                //j*(i-j)代表把i拆分为j和i-j两个数相乘
                //j*dp[i-j]代表把i拆分成j和继续把(i-j)这个数拆分，取(i-j)拆分结果中的最大乘积与j相乘
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}*/
/**
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];

        for (int i = 0; i < m; i++) {
            if (obstacleGrid[0][i] == 1) break; //一旦遇到障碍，后续都到不了
            dp[0][i] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[i][0] == 1) break; ////一旦遇到障碍，后续都到不了
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[n - 1][m - 1];
    }
}*/
/**
class Solution {
    public static List<Integer> findKDistantIndices(int[] nums, int key, int k) {

        List<Integer> list = new ArrayList<Integer>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == key) {
                set.add(i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            for (Integer integer : set) {
                if (Math.abs(i-integer) <= k) {
                    list.add(i);
                    break;
                }
            }
        }
        return list;
    }

}*/
/**
class Solution {
    public int uniquePaths(int m, int n) {
        int [][]dp=new int [m][n];
        for(int i=0;i<m;i++)
        {
            dp[i][0]=1;
        }
        for(int j=0;j<n;j++)
        {
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}*/
/**
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}*/
/**
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        Map<Node,Node>nodemap=new HashMap<>();
        for(Node x=head;x!=null;x=x.next)
        {
            Node node=new Node(x.val);
            nodemap.put(x,node);
        }
        for(Node x=head;x!=null;x=x.next)
        {
            nodemap.get(x).next=nodemap.get(x.next);
            nodemap.get(x).random=nodemap.get(x.random);
        }
        return nodemap.get(head);
    }
}
*/
/**
class Solution {
    public static int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        int length = s.length();
        char[] chars = s.toCharArray();
        int flag = length;
        for (int i = length - 1; i >= 1; i--) {
            if (chars[i] < chars[i - 1]) {
                flag = i;
                chars[i - 1]--;
            }
        }

        for (int i = flag; i < length; i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(new String(chars));

    }

}*/
/**
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length < 2) return 0;

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) {
                    return Integer.compare(o1[1],o2[1]);
                } else {
                    return Integer.compare(o1[0],o2[0]);
                }
            }
        });

        int count = 1;
        int edge = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (edge <= intervals[i][0]){
                count ++; //non overlap + 1
                edge = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}*/
/**
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int cash_5 = 0;
        int cash_10 = 0;

        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                cash_5++;
            } else if (bills[i] == 10) {
                cash_5--;
                cash_10++;
            } else if (bills[i] == 20) {
                if (cash_10 > 0) {
                    cash_10--;
                    cash_5--;
                } else {
                    cash_5 -= 3;
                }
            }
            if (cash_5 < 0 || cash_10 < 0) return false;
        }

        return true;
    }
}
*/
/**
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec;
                pre = 1;
            }
        }
        return ret;
    }
}*/
/**
 class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}*/
/**
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);
            if (count <= 0){
                count = 0;
            }
        }
        return sum;
    }
}*/
/**
class Solution {
    List<List<Integer>>ret=new LinkedList<>();
    LinkedList<Integer>queue=new LinkedList<>();
    int sum=0;
    public List<List<Integer>> combinationSum3(int k, int n) {

        dfs(n,k,1);
        return ret;

    }
    public void dfs(int n,int k,int start)
    {

        if(sum>n)
        {
            return ;
        }
        if(k==queue.size())
        {
            if(sum==n)
            {
                ret.add(new ArrayList<>(queue));
                return;
            }
        }
        for(int i=start;i<10;i++)
        {
            sum+=i;
            queue.add(i);
            dfs(n,k,i+1);
            sum-=i;
            queue.removeLast();
        }
    }
}*/
/**
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};


class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; --i) {
                stack.push(node.children.get(i));
            }
        }
        return res;
    }
}*/
/**
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //得到当前差值
            curDiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}*/
/**
class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return new String(arr);
    }

    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}*/
/**
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}*/
/**
class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}*/
/**
class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i < n; i++)
            if (isPrime[i])
                for (int j = i * i; j < n; j += i)
                    isPrime[j] = false;

        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrime[i]) count++;

        return count;
    }
}*/
/**
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}*/
/**
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}*/
/**
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int head=1;
        int tail=n;

        while(head<tail)
        {
            int mid=head+(tail-head)/2;
            if(isBadVersion(mid))
            {
                tail=mid;
            }
            if(isBadVersion(mid)==false)
            {
                head=mid+1;
            }
        }
        return head;
    }
}
*/
/**
class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}*/
/**
class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean negative = num < 0;
        num = Math.abs(num);
        StringBuffer digits = new StringBuffer();
        while (num > 0) {
            digits.append(num % 7);
            num /= 7;
        }
        if (negative) {
            digits.append('-');
        }
        return digits.reverse().toString();
    }
}*/

/**
class Solution {
    public int sumBase(int n, int k) {
        int sum=0;
        while(n!=0)
        {
            sum+=n%k;
            n=n/k;
        }
        return sum;
    }
}*/
/**
 class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        int n=s.length();
        for (int i = 1; i <=n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}*/
/**
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count=0;
        int x=0;
        int y=0;
        int i=0;
        while(x<s.length)
        {
            for( i=y;i<g.length;i++)
            {
                if(s[x]>=g[i])
                {
                    count++;
                    ++y;
                    break;
                }

            }
            x++;
        }
        return count;

    }
}*/
/**
class Solution {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        //先要找符合出发的索引，然后开始循环
        int sum=0;
        for(int i=0;i<gas.length;i++)
        {
            sum+=gas[i]-cost[i];
        }
        if(sum<0)
        {
            return -1;
        }
        int tank=0;
        int start=0;
        for(int i=0;i<gas.length;i++)
        {
            tank+=gas[i]-cost[i];
            if(tank<0)
            {
                tank=0;
                start=i+1;
            }
        }
        return start;

    }
}*/
/**
class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;

        int[] g = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] == security[i - 1]) continue;
            g[i] = security[i] > security[i - 1] ? 1 : -1;
        }
        int[] a = new int[n + 1], b = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = a[i - 1] + (g[i - 1] == 1 ? 1 : 0);
        for (int i = 1; i <= n; i++) b[i] = b[i - 1] + (g[i - 1] == -1 ? 1 : 0);
        List<Integer> ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            int c1 = a[i + 1] - a[i + 1 - time], c2 = b[i + 1 + time] - b[i + 1];
            if (c1 == 0 && c2 == 0) ans.add(i);
        }
        return ans;
    }
}*/
/**
class Solution {
    private class Freq implements Comparable<Freq>
    {
        private String key;
        private int times;
        public Freq(String key,int times)
        {
            this.key=key;
            this.times=times;
        }
        @Override
        public int compareTo(Freq o)
        {
            return o.times-this.times;
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer>map=new HashMap<>();
        for(int  i=0;i<words.length;i++)
        {
            if(map.containsKey(words[i]))
            {
                map.put(words[i],map.get(words[i])+1);
            }
            else
            {
                map.put(words[i],1);
            }
        }
        Queue<Freq>queue=new PriorityQueue<>();
        for(Map.Entry<String,Integer>entry:map.entrySet())
        {
            if(queue.size()<k)
            {
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }
            else
            {
                Freq l=queue.peek();
                if(entry.getValue()<l.times)
                {
                    continue;
                }

                else
                {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        List<String>ret=new ArrayList();
        for(int i=0;i<k;i++)
        {String c=queue.poll().key;
            ret.add(c);
        }
        return ret;
    }
}*/
/**
class Solution {
    public int maxProduct(int[] nums) {
        PriorityQueue<Integer>queue=new PriorityQueue<Integer>(new Comparator<Integer>()
        {
            @Override
            public int compare(Integer o1,Integer o2)
            {
                return o2-o1;
            }
        });
        for(int i:nums)
        {
            queue.offer(i);
        }
        int x=queue.poll();
        int y=queue.poll();
        return (x-1)*(y-1);

    }
}*/
/**
class Solution {
    public int lastStoneWeight(int[] stones) {

        Queue<Integer>queue=new PriorityQueue<>(new Comparator<Integer>()
        {
            @Override
            public int compare(Integer o1,Integer o2)
            {
                return o2-o1;
            }
        });
        for(int i:stones)
        {
            queue.offer(i);
        }
        while(queue.size()>1)
        {
            int y=queue.poll();
            int x=queue.poll();
            if(x==y)
            {
                continue;
            }
            else
            {
                int z=y-x;
                queue.offer(z);
            }
        }return queue.isEmpty() ? 0 : queue.poll();
    }
}*/
/**
class Solution {
    public int compareVersion(String v1, String v2) {
        int i = 0, j = 0;
        int n = v1.length(), m = v2.length();
        while(i < n || j < m)
        {
            int num1 = 0, num2 = 0;
            while(i < n && v1.charAt(i) != '.')
            { num1 = num1 * 10 + v1.charAt(i++) - '0';}
            while(j < m && v2.charAt(j) != '.')
            {num2 = num2 * 10 + v2.charAt(j++) - '0';}
            if(num1 > num2) return 1;
            else if( num1 < num2) return -1;
            i++; j++;
        }
        return 0;
    }
}*/
/**
class Solution {
    public int findLUSlength(String a, String b) {
        if(a.equals(b))
        {
            return -1;
        }
        else
        {
            char[]arr=a.toCharArray();
            char[]nums=b.toCharArray();
            return Math.max(arr.length,nums.length);
        }
    }
}*/
/**
class Solution {
    public long subArrayRanges(int[] nums) {
        long ans=0;
        for(int i=0;i<nums.length;i++){
            int max=nums[i],min=max;
            for(int j=i+1;j<nums.length;j++){
                min=Math.min(min,nums[j]);
                max=Math.max(max,nums[j]);
                ans+=max-min;
            }
        }
        return ans;
    }
}*/
/**
class Solution {
    public int[] smallestK(int[] arr, int k) {
        if(arr.length==0||k==0)
        {
            return new int[0];
        }

        Queue<Integer>queue=new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2)
            {
                return o2-o1;
            }
        });
        for(int i:arr)
        {
            if(queue.size()<k)
            {
                queue.offer(i);
            }
            else
            {
                int peek=queue.peek();
                if(i>peek)
                {
                    continue;
                }
                else
                {
                    queue.poll();
                    queue.offer(i);
                }
            }
        }
        int []ret=new int [k];
        for(int i=0;i<k;i++)
        {
            ret[i]=queue.poll();
        }
        return ret;
    }
}*/
/**
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) /2;
            if (guess(mid) <= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}*/
/**
class Solution {
    private class Freq implements Comparable<Freq>
    { //把数字和数字出现的次数捆绑
        private int key;
        private int times;
        public Freq(int key,int times)
        {
            this.key=key;
            this.times=times;
        }

        @Override//最小堆的比较器
        public int compareTo(Freq o)
        {
            return this.times-o.times;
        }
    }
    public int []topKFrequent(int []nums,int k)
    {
        int []ret=new int [k];
        Map<Integer,Integer>map=new HashMap<>();
        for(int i:nums)
        {
            if(map.containsKey(i))
            {
                map.put(i,map.get(i)+1);
            }
            else
            {
                map.put(i,1);
            }
        }

        Queue<Freq>queue=new PriorityQueue<>();
        for(Map.Entry<Integer,Integer>entry:map.entrySet())
        {
            if(queue.size()<k)
            {
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }
            else{
                Freq l=queue.peek();
                if(entry.getValue()<l.times)
                {
                    continue;
                }
                else
                {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        for(int i=0;i<k;i++)
        {
            ret[i]=queue.poll().key;
        }
        return ret;

    }

}*/
/**
class Solution {
    private class Pair{
        int u;
        int v;
        public Pair(int u,int v)
        {
            this.u=u;
            this.v=v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        Queue<Pair>queue=new PriorityQueue<>(new Comparator<Pair>()
        {
            @Override
            public int compare(Pair o1,Pair o2)
            {
                return (o2.v+o2.u)-(o1.v+o1.u);
            }
        });

        for(int i=0;i<Math.min(nums1.length,k);i++)
        {
            for(int j=0;j<Math.min(nums2.length,k);j++)
            {
                if(queue.size()<k)
                {
                    queue.offer(new Pair(nums1[i],nums2[j]));
                }
                else
                {
                    int add=nums1[i]+nums2[j];
                    Pair pair=queue.peek();
                    if(add>(pair.u+pair.v))
                    {
                        continue;
                    }
                    else
                    {
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j]));
                    }

                }
            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && (!queue.isEmpty()); i++) {
            List<Integer> temp = new ArrayList<>();
            Pair pair = queue.poll();
            temp.add(pair.u);
            temp.add(pair.v);
            ret.add(temp);
        }
        return ret;

    }
}*/
/**
class Solution {
    public int mySqrt(int x) {
        // 二分搜索
        int left = 0, right = x;
        while(left < right){
            int mid = left + right >> 1;
            if((long) mid * mid < x){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return (long)right * right <= x ? right : right - 1;
    }
}*/
/**
class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1;

    }
}*/

/**
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}*/
/**
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);

        int sum=0;
        for(int i=0;i<nums.length;i+=2)
        {
            sum+=Math.min(nums[i],nums[i+1]);
        }
        return sum;
    }
}*/
/**
class Solution {
    public void moveZeroes(int[] nums) {
        int countZero = 0;
        for (int i = 0; i < nums.length; i++) {
            nums[i - countZero] = nums[i];
            if (nums[i] == 0){
                countZero++;
            }
            if (countZero > 0){
                nums[i] = 0;
            }
        }
    }
}*/
/**
class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        for (int d = n; d / 5 > 0; d = d / 5) {
            res += d / 5;
        }
        return res;
    }
}*/

/**
 class TreeNode {
      int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
          this.right = right;
     }
  }

class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> path = new LinkedList<TreeNode>();
        int pos = 0;//记录遍历的位置
        while (pos < traversal.length()) {
            int level = 0;//层数
            while (traversal.charAt(pos) == '-') {
                ++level;
                ++pos;
            }//遍历到数字
            int value = 0;
            while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) {
                value = value * 10 + (traversal.charAt(pos) - '0'); //节点的值
                ++pos;
            }
            TreeNode node = new TreeNode(value);  //创建节点并且赋值
            if (level == path.size()) {
                //
                if (!path.isEmpty()) {
                    path.peek().left = node;
                }
            }
            else {
                while (level != path.size()) {
                    path.pop();
                }
                path.peek().right = node;
            }
            path.push(node);
        }


        while (path.size() > 1) {
            path.pop();
        }
        return path.peek();
    }
}*/
/**
 class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null)
        {
            return new TreeNode(val);
        }
        if(root.val>val)
        {
            root.left=insertIntoBST(root.left,val);
        }
        if(root.val<val)
        {
            root.right=insertIntoBST(root.right,val);
        }
        return root;
    }
}*/
/**
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[Math.abs(nums[i]) - 1] > 0) {
                nums[Math.abs(nums[i]) - 1] = - nums[Math.abs(nums[i]) - 1];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                results.add(i + 1);
            }
        }
        return results;
    }
}*/
/**
class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder("");
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while(i >= 0 || j >= 0){
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int tmp = n1 + n2 + carry;
            carry = tmp / 10;
            res.append(tmp % 10);
            i--; j--;
        }
        if(carry == 1)
        {res.append(1);}
        return res.reverse().toString();
    }
}*/
/**
class ListNode {
      int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }



   class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int len=0;
        for(ListNode p=head;p!=null;p=p.next)
        {
            len++;
        }
        cur=head;
        return inorderBuild(0,len-1);
    }

    ListNode cur;
    TreeNode inorderBuild(int left,int right)
    {
        if(left>right)
        {
            return null;
        }
        int mid=(right+left)/2;
        TreeNode leftTree=inorderBuild(left,mid-1);
        TreeNode root=new TreeNode(cur.val);
        cur=cur.next;//链表的遍历·
        TreeNode rightTree=inorderBuild(mid+1,right);
        root.left=leftTree;
        root.right=rightTree;
        return root;
    }
}*/
/**
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
         this.right = right;
     }
 }

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}*/
/**
 class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

class Solution {
    private int res, n;

    public int kthLargest(TreeNode root, int k) {
        n = k;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode node) {
        if (node == null || n <= 0) return;
        dfs(node.right);
        if (--n == 0) {
            res = node.val;
            return;
        }
        dfs(node.left);
    }
}*/
/**
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int val,Node left,Node right) {
        val = val;
        left = left;
        right = right;
    }
};


class Solution {
    Node pre = null, head = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node root){
        if (root == null) return;
        dfs(root.left);
        if (pre != null) pre.right = root;
        else head = root;
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}*/
/**
class Solution {
    public int prefixCount(String[] words, String pref) {
        int cnt = 0;
        for (String s : words) if (s.startsWith(pref)) cnt++;
        return cnt;
    }
}*/
 /**class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;

        class Solution {

            public TreeNode increasingBST(TreeNode root) {
                if (root == null) {
                    return null;
                }
                TreeNode left = increasingBST(root.left);
                root.left = null;
                TreeNode right = increasingBST(root.right);
                root.right = right;
                if (left == null) {
                    return root;
                }
                TreeNode p = left;
                while (p != null && p.right != null) {
                    p = p.right;
                }
                p.right = root;

                return left;
            }
        }*/
        /**
        class Solution {
            public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
                if(root1==null)
                {
                    return root2;
                }
                if(root2==null)
                {
                    return root1;
                }
                root1.val=root1.val+root2.val;
                root1.left=mergeTrees(root1.left,root2.left);
                root1.right=mergeTrees(root1.right,root2.right);
                return root1;

            }
        }*/
        /**
        class Solution {
            public TreeNode sortedArrayToBST(int[] nums) {
                return helper(nums, 0, nums.length - 1);
            }

            public TreeNode helper(int[] nums, int left, int right) {
                if (left > right) {
                    return null;
                }
                int mid = (left + right+1) / 2;

                TreeNode root = new TreeNode(nums[mid]);
                root.left = helper(nums, left, mid - 1);
                root.right = helper(nums, mid + 1, right);
                return root;
            }
        }*/
        /**
        class Solution {
            public int countNodes(TreeNode root) {
                TreeNode l=root,r=root;
                int hl=0;
                int hr=0;
                while(l!=null)
                {
                    l=l.left;
                    hl++;
                }
                while(r!=null)
                {
                    r=r.right;
                    hr++;
                }
                if(hl==hr)
                {
                    return (int)Math.pow(2,hl)-1;
                }
                return 1+countNodes(root.left)+countNodes(root.right);

            }
        }
/**
        class Solution {
            private int count = 0;

            public int sumOfLeftLeaves(TreeNode root) {
                if (root == null) {
                    return 0;
                }

                if (root.left != null &&
                        root.left.left == null && root.left.right == null) {
                    count += root.left.val;
                }
                sumOfLeftLeaves(root.left);
                sumOfLeftLeaves(root.right);
                return count;
            }
        }
    }
}*/
/**
class Solution {
    public int maximumDifference(int[] nums) {
        int minValue=0;
        for(int i=0;i<nums.length;i++)
        {
            for(int j=i+1;j<nums.length;j++)
            {
                minValue=Math.max(minValue,nums[j]-nums[i]);
            }
        }
        if(minValue>0)
        {
            return minValue;
        }
        return -1;
    }
}*/
/**
class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int []arr=new int[num_people];
        int n=1;
        int i=0;
        while(candies>0)
        {

            if(candies<n)
            {
                arr[i%num_people]+=candies;
                return arr;
            }

            candies=candies-n;
            arr[i%num_people]+=n;
            n++;
            i++;
        }
        return arr;
    }
}*/
/**
 class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    private StringBuilder sb=new StringBuilder(); //装载字符串的容器
    public String tree2str(TreeNode root) {  //先序遍历，22
        if(root==null)
        {
            return "";  //边界条件
        }
        //存在根节点，
        sb.append(root.val);  //添加根节点的值
        if(root.left!=null)  //如果根节点的左子树不为空（处理左子树）
        {
            sb.append("(");  // 从该根节点开始往子树开始遍历
            tree2str(root.left);//给你一个节点，返回一个字符串
            sb.append(")");//该节点遍历完毕，将字符全部包起来
        }
        else//左子树为空，
        {
            if(root.right!=null)//如果右子树不为空，返回一个（）占位
            {
                sb.append("()");
            }
        }
//如果右子树为空，不必占位和处理
        if(root.right!=null)  //同左树相同操作
        {
            sb.append("(");
            tree2str(root.right);
            sb.append(")");
        }
        return sb.toString();
    }
}*/
/**
class Solution { //最大直径
    private int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 边界
        if (root == null || (root.left == null && root.right == null)) {
            // 空树或只有根节点，不可能存在边
            return 0;
        }
        height(root);
        return max;
    }
    // 递归去求每个节点的高度
    private int height(TreeNode root) {//给你一个根节点，返回该根节点的深度
        if (root == null) {
            return 0;
        }
        // 计算左子树高度
        int l = height(root.left);
        // 计算右子树高度
        int r = height(root.right);
        max = Math.max(max,(l + r));  //记录每个根节点的左右高度之和，并且更新最大值
        // 返回值是求树的深度
        return 1 + Math.max(l,r); //根节点在主函数内已经处理完毕。
    }
}
*/
/**
class Solution {  //找到haystack中首次出现needle首个字符， 首字符相同并且保证needle.length-1-i的字符也完全相同
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {  //循环不断更新haystack的首字母，并与neddle进行对比
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}*/

/**
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    public boolean isCompleteTree(TreeNode root) {//二叉树完全性检验，层序遍历
        Queue<TreeNode>queue=new LinkedList<>();  //队列
        queue.offer(root);  //根节点入队
        boolean isSecondStep=false;//状态转换标志，状态一为false，状态二维true
        while(!queue.isEmpty())//栈为空的话，所有节点应该处理完毕
        {
            TreeNode cur=queue.poll();   //接受该根节点
            if(!isSecondStep)//状态一
            {
                if(cur.left!=null&&cur.right!=null) //如果左右节点都不为空
                {
                    queue.offer(cur.left); //左节点入队
                    queue.offer(cur.right); //右节点入队
                }
                else if(cur.left!=null) //如果左节点不为空，且右树为空
                {
                    isSecondStep=true;  //状态二
                    queue.offer(cur.left); //左节点入队
                }
                else if(cur.right!=null) //左子树为空，右子树不为空，该情况不符合二叉树的完全性
                {
                    return false;  //返回结果，结束程序
                }
                else//如果该节点为叶子节点，那么它后面的所有节点也必须是叶子节点
                {
                    isSecondStep=true;
                }
            }
            else{ //进入状态二
                if(cur.left!=null||cur.right!=null)
                {
                    return false;
                }
            }
        }
        return true;
    }
}*/
  /**
class Solution {
    public int widthOfBinaryTree(TreeNode root) {//二叉树的最大宽度
        if(root==null) //边界条件
        {
            return 0;
        }
        int maxWidth=0;//记录二叉树每层的宽度
        Queue<NodeWithNum> queue=new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));  //存入一个包装类节点，包括节点和编号
        while(!queue.isEmpty())  //层序遍历
        {
             int levelWidth=0;
            int size=queue.size();  //队列的空间大小
            int L=0;
            int R=0;
            for(int i=0;i<size;i++) //装入每一层的根节点，保证层序遍历
            {
                NodeWithNum cur=queue.poll();
                if(i==0)
                {
                    L=cur.num;  //二叉树最左侧包装类节点
                }
                if(i==size-1)
                {
                    R=cur.num;
                }
                if(cur.node.left!=null)//该包装类左子树不为空，添加入队，并且编号为它根节点的2倍
                {
                    queue.offer(new NodeWithNum(cur.node.left,cur.num*2));
                }
                if(cur.node.right!=null)//右子树不为空，编号为根节点2*n+1
                {
                    queue.offer(new NodeWithNum(cur.node.right,cur.num*2+1));
                }
            }
            levelWidth=R-L+1;
            maxWidth=Math.max(levelWidth,maxWidth);  //不断更新最大宽度，因为最低一层不一定是宽度最大。例：只有一个叶子节点
        }
        return maxWidth;
    }
    private class NodeWithNum
    {
        int num;
        TreeNode node;
        public NodeWithNum(TreeNode node,int num)
        {
            this.node=node;
            this.num=num;
        }
    }
}*/
  /**
class Solution {  //后序遍历的迭代写法
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null)
        {
            return ret;
        }
        Deque<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            List<Integer>curList=new ArrayList<>();
            int size=queue.size();
            for(int i=0;i<size;i++)
            {
                TreeNode cur=queue.poll();
                curList.add(cur.val);
                if(cur.left!=null)
                {
                    queue.offer(cur.left);
                }
                if(cur.right!=null)
                {
                    queue.offer(cur.right);
                }
            }
            ret.add(curList);
        }
        return ret;
    }
}*/
  /**
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left,root.right);
    }
    boolean isMirror(TreeNode left,TreeNode right)
    {
        if(left==null&&right==null)
        {
            return true;
        }
        if(left==null||right==null)
        {
            return false;
        }
        if(left.val!=right.val)
        {
            return false;
        }
        return isMirror(left.left,right.right)&&isMirror(left.right,right.left);
    }
}*/
  /**
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null&&subRoot==null)
        {
            return true;
        }
        if(root==null||subRoot==null)
        {
            return false;
        }
        return  isSameTree(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }
    boolean isSameTree(TreeNode root,TreeNode subRoot)
    {
        if(root==null&&subRoot==null)
        {
            return true;
        }
        if(root==null||subRoot==null)
        {
            return false;
        }
        return root.val==subRoot.val&&isSameTree(root.left,subRoot.left)&&isSameTree(root.right,subRoot.right);
    }
}*/
  /**
class Solution {
    private Map<TreeNode,Integer>nodeHeightMap
            =new HashMap<>();
    public boolean isBalanced(TreeNode root) {

        if(root==null)
        {
            return true;
        }
        int left=0;
        int right=0;
        if(nodeHeightMap.containsKey(root.left))
        {
            left=nodeHeightMap.get(root.left);
        }
        else
        {
            left=hight(root.left);
        }
        if(nodeHeightMap.containsKey(root.right))
        {
            right=nodeHeightMap.get(root.right);
        }
        else
        {
            right=hight(root.right);
        }
        int x=Math.abs(left-right);
        if(x>1)
        {
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int hight(TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        return 1+Math.max(hight(root.left),hight(root.right));

    }
}*/
  /**
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        if(root.left==null&&root.right==null)
        {
            return 1;
        }
        int max=Math.max(maxDepth(root.left),maxDepth(root.right));
        return 1+max;

    }
}*/

  /**
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
        {
            return true;
        }
        if(p==null||q==null)
        {
            return false;
        }
        return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

    }
}*/
/**
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length, idx = 0;
        while (idx < n - 1) {
            if (bits[idx] == 0) idx++;
            else idx += 2;
        }
        return idx == n - 1;
    }
}*/
/**
class Solution {
    public long[] sumOfThree(long num) {
        long []arr=new long [0];
        long []nums=new long [3];
        if(num%3!=0)
        {
            return arr;
        }
        nums[0]=num/3-1;
        nums[1]=num/3;
        nums[2]=num/3+1;
        return nums;

    }
}*/
/**
class Solution {
    public int countPairs(int[] nums, int k) {
        int count=0;
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<=nums.length-1;j++)
            {
                if(nums[i]==nums[j]&&(i*j)%k==0)
                {
                    count++;
                }
            }
        return count;
    }
}*/

/**
class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] transposed = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                transposed[j][i] = matrix[i][j];
            }
        }
        return transposed;
    }
}*/
/**
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        int [][]arr=new int[image.length][image.length];
        int x=0;
        for (int i = 0; i < image.length; i++) {
            for (int j = image.length - 1; j >= 0; j--) {
                arr[i][x] = image[i][j];
                if(arr[i][x]==0)
                {
                    arr[i][x]=1;
                }
                else
                {
                    arr[i][x]=0;
                }
                x++;
            }
            x = 0;
        }
        return arr;
    }
}*/
/**
class Solution {
    public int xorOperation(int n, int start) {
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans ^= (start + i * 2);
        }
        return ans;
    }
}*/
/**
class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> ret = new ArrayList<Integer>();
        for (int n = arr.length; n > 1; n--) {
            int index = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i] >= arr[index]) {
                    index = i;
                }
            }
            if (index == n - 1) {
                continue;
            }
            reverse(arr, index);
            reverse(arr, n - 1);
            ret.add(index + 1);
            ret.add(n);
        }
        return ret;
    }

    public void reverse(int[] arr, int end) {
        for (int i = 0, j = end; i < j; i++, j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}*/
/**
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
 }

class Solution {
    TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,
                inorder,0,inorder.length-1);
    }
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] inorder, int inStart, int inEnd) {
        if(preStart>preEnd)
        {
            return null;
        }
        int rootVal=preorder[preStart];
        int index=0;
        for(int i=inStart;i<=inEnd;i++)
        {
            if(inorder[i]==rootVal)
            {
                index=i;
                break;
            }
        }
        int leftSize=index-inStart;
        TreeNode root=new TreeNode(rootVal);
        root.left=build(preorder,preStart+1,preStart+leftSize,
                inorder,inStart,index-1);

        root.right=build(preorder,preStart+leftSize+1,preEnd,
                inorder,index+1,inEnd);
        return root;
    }
}*/
/**
class Solution {
    public List<Integer> maxScoreIndices(int[] nums) {
        int count[]=new int[nums.length];//前缀和，记录1的个数
        count[0]=nums[0];
        for(int i=1;i<nums.length;i++){count[i]=count[i-1]+nums[i];}
        int max=count[nums.length-1];
        for(int i=0;i<nums.length;i++){max=Math.max(max,count[nums.length-1]-2*count[i]+i+1);}
        List<Integer> ans=new ArrayList<>();
        if(max==count[nums.length-1]){ans.add(0);}
        for(int i=0;i<nums.length;i++){if(max==count[nums.length-1]-2*count[i]+i+1){ans.add(i+1);}}
        return ans;
    }
}*/
/**
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;

        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 0; i < n; i++)
            preSum[i + 1] = preSum[i] + nums[i];

        int res = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)

                if (preSum[i] - preSum[j] == k)
                    res++;

        return res;
    }
}*/
/**
class NumArray {
    private int[]preSum;
    public NumArray(int[] nums) {
        preSum=new int[nums.length+1];
        for(int i=1;i<preSum.length;i++)
        {
            preSum[i]=preSum[i-1]+nums[i-1];
        }
    }

    public int sumRange(int left, int right) {
        return preSum[right+1]-preSum[left];
    }
}
*/
/**
class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        if (a == edges[1][0] || a == edges[1][1]) return a;
        else return b;
    }
}*/
/**
class TreeNode {
     int val;
      TreeNode left;
     TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
     this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length - 1,
                postorder, 0, postorder.length - 1);
    }
    TreeNode build(int[] inorder, int inStart, int inEnd,
                   int[] postorder, int postStart, int postEnd) {

        if (inStart > inEnd) {
            return null;
        }
        int rootVal = postorder[postEnd];
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }
        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, inStart, index - 1,
                postorder, postStart, postStart + leftSize - 1);
        root.right = build(inorder, index + 1, inEnd,
                postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}*/
/**
class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length, cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                        ++cnt;
                    }
                }
            }
        }
        return cnt;
    }
}*/
/**
 class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, 0, preorder.length - 1,
                postorder, 0, postorder.length - 1);
    }

    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        int index = 0;
        for (int i = postStart; i < postEnd; i++) {
            if (postorder[i] == leftRootVal) {
                index = i;
                break;
            }
        }
        int leftSize = index - postStart + 1;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);

        return root;
    }
}*/
  /**
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return  build(nums,0,nums.length-1);
    }
    TreeNode build(int []nums,int lo,int hi)
    {
        if(lo>hi)
        {
            return null;
        }
        int index=-1;int maxVal=Integer.MIN_VALUE;
        for(int i=lo;i<=hi;i++)
        {
            if(maxVal<nums[i])
            {
                index=i;
                maxVal=nums[i];
            }
        }
        TreeNode root=new TreeNode(maxVal);
        root.left=build(nums,lo,index-1);
        root.right=build(nums,index+1,hi);

        return root;
    }
}*/
  /**
class Solution {
    public void flatten(TreeNode root) {
        if(root==null)
        {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        TreeNode left=root.left;
        TreeNode right=root.right;
        root.left=null;
        root.right=left;
        TreeNode p=root;
        while(p.right!=null)
        {
            p=p.right;
        }
        p.right=right;
    }
}*/
/**
class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length == 0) {
            return res;
        }
        backtrack(candidates, 0, target, 0);
        return res;
    }
    LinkedList<Integer> track = new LinkedList<>();
    void backtrack(int[] candidates, int start, int target, int sum) {
        if (sum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            track.add(candidates[i]);
            sum += candidates[i];
            backtrack(candidates, i , target, sum);
            sum -= candidates[i];
            track.removeLast();
        }
    }
}*/
/**
class LIKOU {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            int cur_area = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(res, cur_area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}*/
/**
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int sum=numBottles;
        while(numBottles/numExchange>0)
        {
            sum++;
            numBottles=numBottles-numExchange;
            numBottles++;
        }
        return sum;
    }
}*/
/**
class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ans = 0;
        for(int i = 1; i < timeSeries.length; i++){
            ans += Math.min(timeSeries[i] - timeSeries[i - 1], duration);
        }
        ans += duration;
        return ans;
    }
}*/
/**
class Solution {
    public boolean judgeCircle(String moves) {
        char []arr=moves.toCharArray();
        int size=arr.length;
        int col=0;
        int row=0;
        for(int i=0;i<size;i++)
        {
            if(arr[i]=='U')
            {
                col++;
            }
            if(arr[i]=='D')
            {
                col--;
            }
            if(arr[i]=='L')
            {
                row++;
            }
            if(arr[i]=='R')
            {
                row--;
            }
        }
        if(col==0&&row==0)
        {
            return true;
        }
        return false;
    }
}*/
/**
class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
            int num = getValue(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }

    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}*/
/**
 class TreeNode {
     int val;
      TreeNode left;
     TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
     }
  }
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        Queue<TreeNode>q=new LinkedList<>();
        q.offer(root);
        int depth=1;
        while(!q.isEmpty())
        {
            int sz=q.size();
            for(int i=0;i<sz;i++)
            {
                TreeNode cur=q.poll();
                if(cur.left==null&&cur.right==null)
                {
                    return depth;
                }
                if(cur.left!=null)
                {
                    q.offer(cur.left);
                }
                if(cur.right!=null)
                {
                    q.offer(cur.right);
                }
            }
            depth++;
        }
        return depth;
    }
}*/
/**
public  class LIKOU {
    public static void main(String[] args) {
        int n=4;
        int k=2;
        System.out.println(combine(n,k));
    }
   static List<List<Integer>>res=new  LinkedList<>();
    public static List<List<Integer>> combine(int n, int k) {
        if(k<=0||n<=0)
        {
            return res;
        }
        LinkedList<Integer>track=new  LinkedList<>();
        backtrack(n,k,1,track);
        return res;
    }
    static void backtrack(int n, int k, int start, LinkedList<Integer> track)
    {
        if(k==track.size())
        {
           // res.add(new LinkedList(track));
            return;
        }
        for(int i=start;i<=n;i++)
        {
            track.add(i);
            backtrack(n,k,i+1,track);
            track.removeLast();
        }
    }
}*/
/**
class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
    boolean backtrack(char [][]board,int i,int j)
    {
        int m=9,n=9;
        if(j==n)
        {
            return backtrack(board,i+1,0);
        }
        if(i==m)
        {
            return true;
        }
        if(board[i][j]!='.')
        {
            return backtrack(board,i,j+1);
        }
        for(char ch='1';ch<='9';ch++)
        {
            if(!isValid(board,i,j,ch))
            {
                continue;
            }
            board[i][j]=ch;
            if(backtrack(board,i,j+1))
            {
                return true;
            }
            board[i][j]='.';
        }
        return false;
    }

    boolean isValid(char [][]board,int r,int c,char n)
    {
        for(int i=0;i<9;i++)
        {
            if(board[r][i]==n)
            {
                return false;
            }
            if(board[i][c]==n)
            {
                return false;
            }
            if(board[(r/3)*3+i/3][(c/3)*3+i%3]==n)
            {
                return false;
            }
        }
        return true;
    }
}*/
/**
class Solution {
    List<List<Integer>>res=new  LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        if(k<=0||n<=0)
        {
            return res;
        }
        LinkedList<Integer>track=new  LinkedList<>();
        backtrack(n,k,1,track);
        return res;
    }
    void backtrack(int n,int k,int start, LinkedList<Integer>track)
    {
        if(k==track.size())
        {
            res.add(new LinkedList(track));
            return;
        }
        for(int i=start;i<=n;i++)
        {
            track.add(i);
            backtrack(n,k,i+1,track);
            track.removeLast();
        }
    }
}*/
/**
class Solution {
    int N = 55;
    int[] row = new int[N], col = new int[N];
    public List<Integer> luckyNumbers (int[][] mat) {
        int n = mat.length, m = mat[0].length;
        for (int i = 0; i < n; i++) {
            row[i] = 100001;
            for (int j = 0; j < m; j++) {
                row[i] = Math.min(row[i], mat[i][j]);
                col[j] = Math.max(col[j], mat[i][j]);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int t = mat[i][j];
                if (t == row[i] && t == col[j]) ans.add(t);
            }
        }
        return ans;
    }
}*/
/**
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;

    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            backtrack(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}*/

/**
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}*/
/**
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid;
            } else {
                if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[r];
    }
}*/
/**
class Solution {
    public int countOperations(int num1, int num2) {
        int count=0;
        while(num1!=0&&num2!=0)
        {
            if(num1>=num2)
            {
                num1=num1-num2;
            }
            else
            {
                num2=num2-num1;
            }
            count++;
        }
        return count;
    }
}*/
/**
class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] cnts = new int[5];
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c == 'b') cnts[0]++;
            else if (c == 'a') cnts[1]++;
            else if (c == 'l') cnts[2]++;
            else if (c == 'o') cnts[3]++;
            else if (c == 'n') cnts[4]++;
        }
        cnts[2] /= 2; cnts[3] /= 2;
        int ans = cnts[0];
        for (int i = 0; i < 5; i++) ans = Math.min(ans, cnts[i]);
        return ans;
    }
}*/
/**
class Solution {
    public int hammingDistance(int x, int y) {
        int count=0;
        int z=x^y;
        while(z!=0)
        {
            z=z&(z-1);
            count++;
        }
        return count;
    }
}*/
/**
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int size=nums.length;
        Arrays.sort(nums);
        return nums[size-k];

    }
}*/
/**
class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] cnts = new int[5];
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c == 'b') cnts[0]++;
            else if (c == 'a') cnts[1]++;
            else if (c == 'l') cnts[2]++;
            else if (c == 'o') cnts[3]++;
            else if (c == 'n') cnts[4]++;
        }
        cnts[2] /= 2; cnts[3] /= 2;
        int ans = cnts[0];
        for (int i = 0; i < 5; i++) ans = Math.min(ans, cnts[i]);
        return ans;
    }
}*/

/**
public  class LIKOU
{
   static int n,V;
   static int maxn=30;
    static int []w=new int [maxn];
    static int []c=new int [maxn];
    static int ans=0;
    static void DFS(int index, int sumW, int sunC)
    {
        if(index==n)
        {
            return;
        }
        DFS(index+1,sumW,sunC);
        if(sumW+w[index]<=V)
        {
            if(sunC+c[index]>ans)
            {
                ans=sunC+c[index];
            }
            DFS(index+1,sumW+w[index],sunC+c[index]);
        }

    }
    public static void main(String[] args) {
        int maxValue=0;
        Scanner stdin=new Scanner(System.in);
        n=stdin.nextInt();
        V=stdin.nextInt();
        for(int i=0;i<n;i++)
        {
            w[i]=stdin.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            c[i]=stdin.nextInt();
        }
        DFS(0,0,0);
        System.out.println(ans);
    }

}
*/
/**
import javax.management.StandardMBean;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new LinkedList<>();

        return build(1, n);
    }
    List<TreeNode> build(int lo, int hi) {
        List<TreeNode> res = new LinkedList<>();
        // base case
        if (lo > hi) {
            res.add(null);
            return res;
        }
        for (int i = lo; i <= hi; i++) {
            List<TreeNode> leftTree = build(lo, i - 1);
            List<TreeNode> rightTree = build(i + 1, hi);
            for (TreeNode left : leftTree) {
                for (TreeNode right : rightTree) {
                    // i 作为根节点 root 的值
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
}*/
  /**
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null)
        {
            return null;
        }
        if(root.val>val)
        {
            return searchBST(root.left,val);
        }
        if(root.val<val)
        {
            return searchBST(root.right,val);
        }
        return root;
    }
}*/
  /**
class Solution {
    LinkedList<Integer> res=new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        treaese(root);
        return res;
    }
    void treaese(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        treaese(root.left);
        treaese(root.right);
        res.add(root.val);
    }
}*/
/**
class Solution {
    LinkedList <Integer>res=new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        travese(root);
        return res;
    }
    void travese(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        res.add(root.val);
        travese(root.left);
        travese(root.right);
    }
}*/
/**
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
          this.right = right;
     }
  }
class Solution {
    int depth=0;
    int res=0;
    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }
    void traverse(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        depth++;
        res=Math.max(res,depth);
        traverse(root.left);
        traverse(root.right);
        depth--;
    }
}*/
/**
         class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
      TreeNode(int x) { val = x; }
 }
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
        {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}*/
/**
class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}*/



/**

         class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
      }
  }
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        traverse(root);
        return res;
    }
    LinkedList<String>path=new LinkedList<>();
    LinkedList<String>res=new LinkedList<>();
    void traverse(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        if(root.left==null&&root.right==null)
        {
            path.addLast(root.val+"");
            res.addLast(String.join("->",path));
            path.removeLast();
            return;
        }
        path.addLast(root.val+"");
        traverse(root.left);
        traverse(root.right);
        path.removeLast();
    }
}*/
/**
class Solution {
    List<List<Integer>>res =new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer>track=new LinkedList<>();
        backtrack(nums,track);
        return res;
    }
    void backtrack(int []nums,LinkedList<Integer>track)
    {
        if(track.size()==nums.length)
        {
            res.add(new LinkedList(track));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(track.contains(nums[i]))
            {
                continue;
            }
            track.add(nums[i]);
            backtrack(nums,track);
            track.removeLast();
        }
    }
}*/
/**
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;

    }
}*/
/**
 class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
}*/
/**
class Solution {
    public int singleNumber(int[] nums) {
        int reg=0;
        for(int x:nums)
        {
            reg^=x;
        }
        return reg;
    }
}*/
/**
class LIKOU
{
    public static void main(String[] args) {
        int count=0;
        int []nums={1,2,2,1};
        int k=1;
        for(int i=0;i<4;i++)
        {
            for(int j=i+1;j<4;j++)
            {
                int value=Math.abs(nums[i]-nums[j]);
                if(i<j&&value==k)
                {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}*/
/**
class LIKOU {
    public static void main (String[] args){
        String s = "aab";
        String s1 = "baa";
        System.out.println(canConstruct( s, s1));
    }
    public static boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}*/
/**
class Solution {
    public int pivotIndex(int[] nums) {
        int sum1 = 0;
        for(int num: nums){
            sum1 += num;
        }
        int sum2 = 0;
        for(int i = 0; i<nums.length; i++){
            sum2 += nums[i];
            if(sum1 == sum2){
                return i;
            }
            sum1 = sum1 - nums[i];
        }
        return -1;
    }
}*/
/**
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int size=nums.length;
        int j=0;
        int []arr=new int [size];
        for(int i=0;i<size;i++)
        {
            if(nums[i]%2==0)
            {
                arr[j++]=nums[i];
            }
        }
        for(int i=0;i<size;i++)
        {
            if(nums[i]%2!=0)
            {
                arr[j++]=nums[i];
            }
        }
        return arr;
    }
}
*/
/**
class Solution {
    public String reverseOnlyLetters(String s) {
        int i = 0, j = s.length() - 1;
        char[] array = s.toCharArray();
        while (i < j) {
            if (Character.isLetter(array[i]) && Character.isLetter(array[j])) {
                char tmp = array[i]; array[i] = array[j]; array[j] = tmp;
                i ++; j --;
            } else if (!Character.isLetter(array[i])) {
                i ++;
            } else {
                j --;
            }
        }
        return String.valueOf(array);
    }
}*/
/**
class Solution {
    public boolean containsDuplicate(int[] nums) {
        int size=nums.length;
        Set<Integer>set=new HashSet<>();
        if(size==1)
        {
            return false;
        }
        for(int i=0;i<size;i++)
        {
            if(set.contains(nums[i]))
            {
                return true;
            }
            set.add(nums[i]);
        }
        return false;

    }
}*/
/**
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}*/
/**
class Solution {
    public int lengthOfLastWord(String s) {
        int size=s.length();
        int flag=0;
        int count=0;
        if(size==1)
        {
            return 1;
        }
        for(int i=size-1;i>=0;i--)
        {
            char c=' ';
            if(c==s.charAt(i))
            {
                if(flag==2)
                {
                    count=count;
                    break;
                }
                flag=1;
                continue;
            }
            else
            {
                count++;
                flag=2;
            }
        }
        return count;
    }
}*/
/**
class Solution {
    int[] cnt = new int[110];
    public int sumOfUnique(int[] nums) {
        for (int i : nums) cnt[i]++;
        int ans = 0;
        for (int i = 1; i <= 100; i++) {
            if (cnt[i] == 1) ans += i;
        }
        return ans;
    }
}*/
/**
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}
*/
/**
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
*/
/**
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}*/
/**
class Solution {
    public int countValidWords(String sentence) {
        String[] ss = sentence.split(" ");
        int ans = 0;
        for (String s : ss) if (check(s)) ans++;
        return ans;
    }
    boolean check(String s) {
        int n = s.length();
        if (n == 0) return false;
        for (int i = 0, c1 = 0, c2 = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == ' ') return false;
            if (c == '-' && ++c1 >= 0) {
                if (c1 > 1 || (i == 0 || i == n - 1)) return false;
                if (!Character.isLetter(s.charAt(i - 1)) || !Character.isLetter(s.charAt(i + 1))) return false;
            }
            if ((c == '!' || c == '.' || c == ',') && ++c2 >= 0) {
                if (c2 > 1 || (i != n - 1)) return false;
            }
        }
        return true;
    }
}
*/

/**
class Solution {
    private Stack<Integer>s= new Stack<>();
    private Map<Integer,Integer>map=new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
      for(int i=nums2.length;i>=0;i--) {
          while (!s.isEmpty() && s.peek() <= nums2[i]) {
              s.pop();
          }
          int x = s.isEmpty() ? -1 : s.peek();
          s.push(nums2[i]);
          map.put(nums2[i], x);
      }
          int[] reg = new int[nums1.length];

  for(int i=0;i<nums1.length;i++)
  {
      reg[i]=map.get(nums1);
  }

return reg;

    }
}*/
/**
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}
*/
/**
class MyStack {
    private  Queue<Integer >p1=new LinkedList<>();
    private  Queue<Integer>p2=new LinkedList<>();

    public MyStack() {

    }

    public void push(int x) {
            p2.offer(x);
            while(!p1.isEmpty())
            {
                p2.offer(p1.poll());
            }
                Queue<Integer>temp=p1;
            p1=p2;
            p2=temp;


    }
    public int pop() {
        return p1.poll();

    }

    public int top() {
        return p1.peek();

    }

    public boolean empty() {
        return p1.isEmpty();

    }
}*/
/**
class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }
    }
}*/
/**
class MyQueue {
    private Stack<Integer>s1=new Stack<>();
    private  Stack<Integer>s2=new Stack<>();

    public MyQueue() {

    }

    public void push(int x) {
    if(s1.empty())
    {
        s1.push(x);
    }
    else
    {
        while(!s1.empty())
        {
            s2.push(s1.pop());
        }
        s1.push(x);
        while(!s2.empty())
        {
            s1.push(s2.pop());
        }
    }

    }

    public int pop() {
        return s1.pop();

    }

    public int peek() {
        return s1.peek();
    }

    public boolean empty() {
        return s1.empty();

    }
}
*/

/**
class LIKOU {
    public static void main(String[] args) {
      String str="12asasd";
      int count =0;
      for(int i=0;i<str.length();i++) {
          if ((str.charAt(i) >='a' &&str.charAt(i) <= 'z' )|| (str.charAt(i) >='A' && str.charAt(i) <= 'Z')) {
              count++;
          }
      }
      System.out.println(str.length()-count);
    }
}*/
/**
class LIKOU {
    public static void main(String[] args) {
        System.out.println(generate(5));
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);

        }
      return ret;
    }
}*/

/**
class Solution {
    public int convertInteger(int A, int B) {
        int temp = A ^ B;
        int count = 0;
        while (temp != 0) {
            temp &= (temp - 1);  // 去掉二进制表示的最右边的1
            count++;
        }
        return count;
    }
}
*/
/**
class Solution {
    public int removePalindromeSub(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; ++i) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                return 2;
            }
        }
        return 1;
    }
}*/

/**
class Solution {
    public int titleToNumber(String columnTitle) {
        int number = 0;
        int multiple = 1;
        for (int i = columnTitle.length() - 1; i >= 0; i--) {
            int k = columnTitle.charAt(i) - 'A' + 1;
            number += k * multiple;
            multiple *= 26;
        }
        return number;
    }
}*/

/**
class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}*/
/**class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size() * 2;
        int[] nums = new int[n];
        for (int i = 0, idx = 0; i < n / 2; i++, idx += 2) {
            String[] ss = timePoints.get(i).split(":");
            int h = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]);
            nums[idx] = h * 60 + m;
            nums[idx + 1] = nums[idx] + 1440;
        }
        Arrays.sort(nums);
        int ans = nums[1] - nums[0];
        for (int i = 0; i < n - 1; i++) ans = Math.min(ans, nums[i + 1] - nums[i]);
        return ans;
    }
}
*/

/**
class Solution {
    public int dayOfYear(String date) {
        int year = Integer.parseInt(date.substring(0, 4));
        int month = Integer.parseInt(date.substring(5, 7));
        int day = Integer.parseInt(date.substring(8));

        int[] amount = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
            ++amount[1];
        }

        int ans = 0;
        for (int i = 0; i < month - 1; ++i) {
            ans += amount[i];
        }
        return ans + day;
    }
}
*/

/**
class LIKOU
{
    public static void main(String[] args) {
        int n=20;
        int sum=0;
        int count=1;
        int flag=1;
        int temp=0;
        int days=1;
        int days1=1;
        int temp1=temp;
        while(days<=n)
        {
            sum=count++;
            temp+=sum;
            if(days%7==0)
            {
                count=flag+1;
                flag++;
                sum=0;

            }
            days++;
        }
      System.out.println(temp);
    }
}

*/
/**
class LIKOU {
    public String toLowerCase(String s) {
        return s.toLowerCase();

    }
}
*/

/**
class Solution {
    public void reverseString(char[] s) {
        int low=0;
        char cur;
        char cur1;
        int fast=s.length-1;

        while(low<=fast)
        {
            cur=s[low];
            cur1=s[fast];
            s[low]=cur1;
            s[fast]=cur;
            low++;
            fast--;
        }

    }
}*/
/**
class Solution {
    public int dominantIndex(int[] nums) {
        int max=0;
        int size=nums.length;
        int flag=-1;
        int cc=0;
        int []arr=new int[size];
        if(size==1)
        {
            return 0;
        }

        for(int i=0;i<size;i++)
        {
            if(max<nums[i])
            {
                max=nums[i];
            }
        }


        for(int i=0;i<size;i++)
        {
            arr[i]=nums[i]*2;

        }
        for(int i=0;i<size;i++)
        {
            if(max<arr[i])
            {
                flag++;
                cc=i;
            }
        }

        if(flag>0||flag==-1)
        {
            return -1;
        }
        else
        {
            return cc;
        }

    }
}*/
/**
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}*/
/**
class Solution {
    public int calPoints(String[] ops) {

        List<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i < ops.length; ++i){
            if(ops[i].equals("C")){
                list.remove(list.size() - 1);

            } else if(ops[i].equals("D")){
                list.add(list.get(list.size() - 1) * 2);

            } else if(ops[i].equals("+")){
                list.add(list.get(list.size() - 2) + list.get(list.size() - 1));
            } else{

                list.add(Integer.valueOf(ops[i]));
            }
        }

        int sum = 0;
        for(int elem : list){
            sum += elem;
        }
        return sum;
    }
}*/


/**
class Solution {

    public int addDigits(int num) {
        while (num >= 10) {
            int next = 0;
            while (num != 0) {
                next = next + num % 10;
                num /= 10;
            }
            num = next;
        }
        return num;

    }
}*/

/**
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            String cur = "";
            if (i % 3 == 0) cur += "Fizz";
            if (i % 5 == 0) cur += "Buzz";
            if (cur.length() == 0) cur = i + "";
            ans.add(cur);
        }
        return ans;
    }
}

*/
/**
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
            }
            map.put(nums[i], i);
        }
        return res;
    }
}*/
/**
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
            }
            map.put(nums[i], i);
        }
        return res;
    }
}*/
/**
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}*/
/**
class LIKOU {
    public static void main(String[] args) {
        int []nums1=new int [4];
        nums1[0]=1;  nums1[1]=2;  nums1[2]=3;  nums1[3]=2;
        int []nums2=new int [2];
        nums2[0]=2; nums2[1]=3;
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : resSet) {
            resArr[index++] = i;
        }

    }
}*/
/**
class Solution {
    public int maxDepth(String s) {
        int size=101;
        int count=0;
        int flag=s.length();
        int []nums=new int [flag];
        char[] arr = s.toCharArray();
        int j=0;
        for(int i=0;i<flag;i++)
        {
            if(arr[i]=='(')
            {
                count++;
                nums[j++]=count;
            }
            if(arr[i]==')')
            {
                count--;
            }
        }
        Arrays.sort(nums);
        if(nums[flag-1]>0)
        {
            return nums[flag-1];
        }
        else
        {
            return 0;
        }
    }
}*/
/**
class Solution {
    public int removeElement(int[] nums, int val) {
        int size = 0;
        int Long = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                nums[i] = 101;
                size++;
            }
        }
        Arrays.sort(nums);
        Long = nums.length - size;
        return Long;

    }
}*/
/**
class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i=0;i<nums.length;i++)
        {
            nums[i]=nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}*
/**
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        if(result==Integer.MAX_VALUE)
        {
            return 0;
        }
        else
        {
            return result;
        }
    }
}*/
/**
class Solution {
    public String modifyString(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; ++i) {
            if (arr[i] == '?') {
                for (char ch = 'a'; ch <= 'c'; ++ch) {
                    if ((i > 0 && arr[i - 1] == ch) || (i < n - 1 && arr[i + 1] == ch)) {
                        continue;
                    }
                    arr[i] = ch;
                    break;
                }
            }
        }
        return new String(arr);
    }
}*/
/**
class Solution {
    public int search(int[] nums, int target) {

        int head=0;
        int tail=nums.length-1;
        int mid=nums.length/2;
        while(head<=tail)
        { mid = (tail - head) / 2 + head;
            if(nums[mid]==target)
            {
                return mid;
            }
            if(nums[mid]<target)
            {
                head=mid+1;
            }
            else
            {
                tail=mid-1;
            }
        }
        return -1;
    }
}*/
/**
class LIKOU
{
    public static void main(String[] args)

    {
        int []nums=new int[3];
        int target=2;
       nums[0]=2;
       nums[1]=3;
       nums[2]=4;

        int head=0;
        int tail=nums.length;
        int mid=nums.length/2;

        while(head!=mid)
        {
            if(nums[mid]<target)
            {
                head=mid;

            }
            if(nums[mid]>target)
            {
                tail=mid;

            }
            mid=(head+tail)/2;
            if(nums[mid]==target)
            {
                System.out.println(mid);
                break;
            }
        }

       System.out.println("-1");
    }
}
*/


/**
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode node=head;
        ListNode dummy=new ListNode(101);
        ListNode prev=dummy;
        int count=0;
        int size=0;
        if(head==null)
        {
            return null;
        }
        while(node!=null)
        {
            node=node.next;
            count++;
        }
        int []arr=new int [count];
        while(head!=null)
        {
            arr[size++]=head.val;
            head=head.next;
        }
        Arrays.sort(arr);
        for(int i=0;i<count;i++)
        {
            ListNode node1=new ListNode(1000000);
            node1.val=arr[i];
            prev.next=node1;
            prev=prev.next;
        }
        return dummy.next;
    }
}*/
/**
 class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode prev=head;
        int count=0;
        int i=0;
        ListNode dummy=new ListNode(101);
        while(prev!=null)
        {
            ListNode node=new ListNode(prev.val);
            node.next=dummy.next;
            dummy.next=node;
            count++;
            prev=prev.next;
        }
        int []arr=new int [count];
        ListNode cur=dummy.next;
        while(cur!=null)
        {
            arr[i++]=cur.val;
            cur=cur.next;
        }
        return arr;
    }
}*/
/**
 class ListNode {
    int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution {

    public boolean isPalindrome(ListNode head) {

        ListNode dunmmy =new ListNode(101);

        ListNode Newhead;

        ListNode fast=head;

        ListNode low=head;

        if(head.next==null)

        {

            return true;

        }

        while(fast!=null&&fast.next!=null)

        {

            fast=fast.next.next;

            low=low.next;

        }

        Newhead=low;

        while(Newhead!=null)

        {

            ListNode node=new ListNode(Newhead.val);

            node.next=dunmmy.next;

            dunmmy.next=node;

            Newhead=Newhead.next;

        }

        Newhead=dunmmy.next;

        while(Newhead!=null)

        {

            if(head.val!=Newhead.val)

            {

                return false;

            }

            head=head.next;

            Newhead=Newhead.next;

        }

        return true;

    }

}*/
/**
//剑指 Offer 18. 删除链表的节点
 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
  }

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode node=head;
        if(head.val==val)
        {
            return head.next;
        }
        while(node.next.val!=val)
        {
            node=node.next;
        }
        node.next=node.next.next;
        return head;
    }
}*/
/**
//24两两交换相邻节点
 class ListNode {
      int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode swapPairs(ListNode head) {

        if(head==null)
        {
            return null;
        }
        if(head.next==null)
        {
            return head;
        }

        else
        {
            ListNode prev=head;
            ListNode dummy=new ListNode();
            ListNode node2=dummy;
            while(prev!=null&&prev.next!=null)
            {
                ListNode node=new ListNode(prev.next.val);
                ListNode node1=new ListNode(prev.val);
                node2.next=node;
                node.next=node1;
                node2=node1;
                prev=prev.next.next;
            }
            node2.next=prev;

            return dummy.next;
        }
    }
}*/
/**
class Solution {
    public int lastRemaining(int n) {
        int head = 1;
        int step = 1;
      int left=0;


        while (n > 1) {
            left=0;
            if (left==0 || n % 2 != 0) {
                head += step;
            }
            step *= 2; //步长 * 2
            left=1; //取反移除方向
            n /= 2; //总数 / 2
        }

        return head;
    }
}
*/

/**
//反转链表
 class ListNode {

    int val;

    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

}



class Solution {

    public ListNode reverseList(ListNode head) {

        ListNode dummp=new ListNode(101);

        if(head==null||head.next==null)

        {

            return head;

        }

        while(head!=null)

        {

            ListNode node=new ListNode(head.val);

            node.next=dummp.next;

            dummp.next=node;

            head=head.next;



        }

        return dummp.next;

    }

}*/
/**
//回文链表
 class ListNode {

    int val;

    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

}



class Solution {

    public boolean isPalindrome(ListNode head) {

        ListNode dunmmy =new ListNode(101);

        ListNode Newhead;

        ListNode fast=head;

        ListNode low=head;

        if(head.next==null)

        {

            return true;

        }

        while(fast!=null&&fast.next!=null)

        {

            fast=fast.next.next;

            low=low.next;

        }

        Newhead=low;

        while(Newhead!=null)

        {

            ListNode node=new ListNode(Newhead.val);

            node.next=dunmmy.next;

            dunmmy.next=node;

            Newhead=Newhead.next;

        }

        Newhead=dunmmy.next;

        while(Newhead!=null)

        {

            if(head.val!=Newhead.val)

            {

                return false;

            }

            head=head.next;

            Newhead=Newhead.next;

        }

        return true;

    }

}
*/

/**
class ListNode{

    int val;

    ListNode next;

    ListNode(int x){

        val=x;

        next=null;

    }

}*/

/** 唤醒链表的入口
public class LIKOU
{
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;
        int count = 0;
        if (head.next == null) {
            return null;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if (fast == low) {
                ListNode third = head;
                while (third != head) {
                    third = third.next;
                    low = low.next;
                }
                return low;
            }
        }
        return null;
    }
}
/**
public class 力扣 {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;

    while(fast!=null||fast.next!=null)
    {
        fast=fast.next.next;
        low=low.next;
        if(fast.val==low.val)
        {
            return true;
        }
    }
   return false;
    }
}*/
